package Algorithms.classic;

/**
 * description: <br>
 * createTime: 2020/9/116:12 <br>
 *
 * @author zzh
 */
public class HeapSortTest {

    public static void main(String[] args) {
        SortUtils.test(HeapSortTest::heapSort);
    }


    private static int[] heapSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int currentIndex = i;
            int temp = array[i];
            while (currentIndex > 0) {
                int parentIndex = (currentIndex - 1) / 2;
                if(temp <= array[parentIndex]) {
                    break;
                }
                array[currentIndex] = array[parentIndex];
                currentIndex = parentIndex;
            }
            array[currentIndex] = temp;
        }
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[i];
            array[i] = array[0];
            int currentIndex = 0;
            while (currentIndex < i / 2) {
                int leftIndex = 2 * currentIndex + 1;
                int rightIndex = 2 * currentIndex + 2;
                int largerIndex;
                if(rightIndex >= i || array[leftIndex] >= array[rightIndex]) {
                    largerIndex = leftIndex;
                } else {
                    largerIndex = rightIndex;
                }
                if(temp >= array[largerIndex]) {
                    break;
                }
                array[currentIndex] = array[largerIndex];
                currentIndex = largerIndex;
            }
            array[currentIndex] = temp;
        }
        return array;
    }
}